package com.shigen.demo.datastruct.hashmap;

/**
 * 手写hashMap
 *
 * @author shigenfu
 * @date 2022/7/14 10:04 下午
 */
public class MyHashMap {

  static class Node {

    private int key;
    private int value;
    private Node next;

    public Node(int key, int value) {
      this.key = key;
      this.value = value;
    }
  }

  // 当前数组的长度
  private int size = 0;
  // 加载因子
  private static final double LOAD_FACTORY = 0.75;
  // 初始长度
  private static final Integer INITIAL_LEN = 3;
  // 数组
  private Node[] array = new Node[INITIAL_LEN];

  /**
   * 获得下标
   */
  private Integer Hash(int key) {
    return key % array.length;
  }

  /**
   * 放入元素
   */
  public void put(int key, int value) {
    int newIndex = Hash(key);
    Node list = array[newIndex];
    // 判断当前key在链表中是否存在，如果存在则替换对应的值
    for (Node cur = list; cur != null; cur = cur.next) {
      if (cur.key == key) {
        cur.value = value;
        return;
      }
    }
    // 新建节点头插
    Node node = new Node(key, value);
    node.next = list;
    array[newIndex] = node;
    size++;
    if (size / array.length > LOAD_FACTORY) {
      resize();
    }
  }

  /**
   * hashMap的扩容
   */
  private void resize() {
    Node[] newArray = new Node[array.length * 2];
    // 开始循环转移元素
    for (int i = 0; i < array.length; i++) {
      for (Node cur = array[i]; cur != null; cur = cur.next) {
        // 新建节点头插
        Node node = new Node(cur.key, cur.value);
        // 获得数组下标，此时是根据新数组的长度取模获得
        int newIndex = cur.key % newArray.length;
        node.next = newArray[newIndex];
        newArray[newIndex] = node;
      }
    }
    array = newArray;
  }

  /**
   * 获得key对应的value
   */
  public Integer get(int key) {
    int index = Hash(key);
    for (Node node = array[index]; node != null; node = node.next) {
      if (node.key == key) {
        return node.value;
      }
    }
    return null;
  }

  /**
   * 移除元素
   */
  public void remove(int key) {
    int index = Hash(key);
    Node list = array[index];
    if (list == null) {
      return;
    }
    // 如果是头节点
    if (list.key == key) {
      array[index] = list.next;
      size--;
      return;
    }
    // 获得对应的链表，在链表中移除
    for (Node node = list.next; node != null; node = node.next) {
      if (node.key == key) {
        list.next = node.next;
        size--;
      }
    }
  }

  /**
   * 获得hashMap的元素个数
   */
  public int getSize() {
    return size;
  }

  /**
   * 打印map中的元素
   */
  public void print() {
    for (int i = 0; i < array.length; i++) {
      if (array[i] != null) {
        for (Node node = array[i]; node!= null; node = node.next) {
          System.out.println(node.key + "\t" + node.value);
        }
      }
    }
  }
}
